package leetcode_2501_2600;

import java.util.Arrays;
import java.util.Comparator;
import java.util.PriorityQueue;

public class LeeCode_2542 {
    public static void main(String[] args) {
//        System.out.println(maxScore(new int[]{1, 3, 3, 2}, new int[]{2, 1, 3, 4}, 3));
        System.out.println(maxScore(new int[]{23,16,20,7,3}, new int[]{19,21,22,22,12}, 3));
    }
    private static long maxScore(int[] nums1, int[] nums2, int k) {
        int n = nums1.length;
        Integer[] is = new Integer[n];
        for (int i = 0; i < n; i++) {
            is[i] = i;
        }
        Arrays.sort(is, (o1, o2) -> nums2[o2] - nums2[o1]);
        int l = k - 1;
        PriorityQueue<Integer> queue = new PriorityQueue<>(Comparator.comparingInt(o -> o));
        long sum = 0;
        for (int i = 0; i < k; i++) {
            queue.add(nums1[is[i]]);
            sum += nums1[is[i]];
        }
        long ans = 0;
        while (l < n){
            while (queue.size() > k){
                int poll = queue.poll();
                sum -= poll;
            }
            ans = Math.max(ans, sum * nums2[is[l]]);
            l++;
            if (l < n) {
                queue.add(nums1[is[l]]);
                sum += nums1[is[l]];
            }
        }
        return ans;
    }
}
